//
// Created by user on 2022/3/7.
//
#include <vector>
#include <algorithm>
using namespace std;
vector<int> partitionLabels(string s) {
    int n = s.length();
    //计算并存储每个字符在数组中所在的最大索引
    vector<int> c2Index(26, 0);
    for (int i = 0; i < n; ++i) {
        c2Index[s[i]-'a'] = i;
    }
    vector<int> res;
    //维护窗口
    int left = 0;
    int right = 0;
    for (int i = 0; i < n; ++i) {
        char c = s[i];
        right = max(right, c2Index[c-'a']);
        if(i==right){
            res.push_back(right-left+1);
            left = right+1;
        }
    }
    return res;
}